package cn.zhl.leetcode.链表;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-04-02 16:11
 * https://leetcode-cn.com/problems/reverse-linked-list/
 **/
public class _206_反转链表 {
	//    输入: 1->2->3->4->5->NULL
//    输出: 5->4->3->2->1->NULL
//    递归方式
	public ListNode reverseList1(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode newNode = reverseList1(head.next);
		head.next.next = head;
		head.next = null;
		return newNode;
	}

	//    非递归方式
	public ListNode reverseList2(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode tmp = null;
		ListNode newNode = null;
		while (head != null) {
			tmp = head.next;
			head.next = newNode;
			newNode = head;
			head = tmp;
		}

		return newNode;
	}
}
